class Solution {
public:
    string longestPalindrome(string s)
    {
        int n = s.length();
        int start = 0, end = 0;
        if(n < 2) {
            return s;
        }
        vector<int> dp(n, 1);
        for(int i = n - 2; i >= 0; --i) {
            for(int j = n - 1; j >= i; --j) {
                if(j - i < 1) {
                    dp[j] = 1;
                } else if(dp[j - 1] && s[i] == s[j]) {
                    dp[j] = 1;
                    if(j - i > end - start) {
                        start = i;
                        end = j;
                    }
                } else {
                    dp[j] = 0;
                }
            }
        }
        return s.substr(start, end - start + 1);
    }
};